/*
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
*/

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        if (points.size() <= 2) return points.size();
        int maxp, dnum, vnum; //vnum -- vertical points
        unordered_map<double, int> slopes;
        for (int i = 0; i < points.size()-1; i++) {
            slopes.clear(); vnum = 0; dnum = 1;
            for (int j = i+1; j < points.size(); j++) {
                if (points[j].x == points[i].x) {
                    if (points[j].y == points[i].y) dnum++; // same point
                    else vnum++; // vertical line
                } else {
                    double slope = double(points[j].y-points[i].y)/(points[j].x-points[i].x);
                    if (slopes.find(slope) == slopes.end()) slopes[slope] = 1; // first point
                    else slopes[slope]++; // found another point
                }
            }
            // compute max points on a line for this anchor point
            if (vnum + dnum > maxp) maxp = vnum + dnum;
            for (auto it = slopes.begin(); it != slopes.end(); it++) {
                if (it->second + dnum > maxp) maxp = it->second + dnum;
            }
        }
        return maxp;
    }
};

#if 0 
class Solution {
public:
    static const int EPSILON = 1000000;  // float precision purpose
    std::unordered_map<int, int> lines;  // We use the unordered_map, key is the slope of the line and value is the count of points
    int find_sub_max_points(vector<Point> &points, int last) {
        lines.clear();  // Clear the hash table
        int num_same_x = 0;  // count the number of points with same x-coordinate of Point[last]
        int num_same_point = 1;
        const int x0 = points[last].x;
        const int y0 = points[last].y;
        int x,y,tmp;
        int res = 0;
        for (int i = last-1; i >= 0; i--) {
            x = points[i].x;
            y = points[i].y;
            if (x == x0) {
                if (y == y0) num_same_point++;
                else if(++num_same_x > res)
                    res = num_same_x;
            }
            else {
                tmp = int( (y-y0) * EPSILON ) / (x-x0);
                if (++lines[tmp] > res) res = lines[tmp];
            }
        }
        return res+num_same_point; // Point[last] itself should be counted
    }
    int maxPoints(vector<Point> &points) {
        int n = points.size();
        if (n <= 2) return n;
        int res = 2;
        int tmp = 0;
        for(int i=2; i<n; i++) {
            tmp = find_sub_max_points(points, i);
            if (tmp > res) res = tmp;
        }
        return res;
    }
};
#endif
